package com.zlk.algorithm.algorithm.dynamicPlan.twoDimension;

/**
 * @program: algorithm
 * @ClassName RobotWalk
 * @description:
 *
 * 假设有排成一行的N个位置记为1~N，N一定大于或等于2 开始时机器人在其中的M位置上(M一定是1~N中的一个)
 * 如果机器人来到1位置，那么下一步只能往右来到2位置； 如果机器人来到N位置，那么下一步只能往左来到N-1位置；
 * 如果机器人来到中间位置，那么下一步可以往左走或者往右走； 规定机器人必须走K步，最终能来到P位置(P也是1~N中的一个)的方法有多少种
 * 给定四个参数 N、M、K、P，返回方法数
 * @author: slfang
 * @create: 2024-09-13 17:14
 * @Version 1.0
 **/
public class RobotWalk {


    public static int ways1(int N, int start, int aim, int K) {
        if (N < 2 || start < 1 || start > N || aim < 1 || aim > N || K < 1) {
            return -1;
        }
        return process1(start, K, aim, N);
    }

    /**
     *
     * @param start 起始位置
     * @param k 规定走的步长
     * @param aim 终点位置
     * @param n 排队长度
     * @return
     */
    private static int process1(int start, int k, int aim, int n) {
        //basecase
        if(k==0){
          return start==aim?1:0;
        }
        if(start==1){
            return process1(start+1,k-1,aim,n);
        }
        if(start==n){
            return process1(start-1,k-1,aim,n);
        }
        return process1(start+1,k-1,aim,n)+process1(start-1,k-1,aim,n);
    }

    /**
     * 记忆化搜索
     * @param start 起始位置
     * @param k 规定走的步长
     * @param aim 终点位置
     * @param n 排队长度
     * @return
     */
    private static int process2(int start, int k, int aim, int n,int[] dp) {
        //basecase

        if(k==0){
            return start==aim?1:0;
        }
        if(start==1){
            return process1(start+1,k-1,aim,n);
        }
        if(start==n){
            return process1(start-1,k-1,aim,n);
        }
        return process1(start+1,k-1,aim,n)+process1(start-1,k-1,aim,n);
    }
}
